package main.Q1_100;

import java.util.ArrayList;
import java.util.List;

public class Q21_30 {
    public static void main(String[] args) {
        System.out.println("Question21：合并两个有序链表");
        System.out.println("Question22：括号生成");
        System.out.println("Question23：合并K个升序链表");
        System.out.println("Question24：两两交换链表中的节点");
        System.out.println("Question25：K个一组翻转链表");
        System.out.println("Question26：删除有序数组中的重复项");
        System.out.println("Question27：移除元素");
        System.out.println("Question28：实现strStr()");
        System.out.println("Question29：两数相除");
        System.out.println("Question30：");
    }
}

class Question21 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                prev.next = list1;
                list1 = list1.next;
            } else {
                prev.next = list2;
                list2 = list2.next;
            }
            prev = prev.next;
        }
        prev.next = list1 == null ? list2 : list1;
        return prehead.next;
    }
}

class Question22 {
    List<String> parentheses = new ArrayList<String>();
    StringBuffer temp = new StringBuffer();
    int n;

    public List<String> generateParenthesis(int n) {
        this.n = n;
        process(0, 0);
        return parentheses;
    }

    public void process(int left, int right) {
        if (temp.length() == 2 * n) {
            parentheses.add(temp.toString());
        } else {
            if (left < n) {
                temp.append('(');
                process(left + 1, right);
                temp.deleteCharAt(temp.length() - 1);
            }
            if (right < left) {
                temp.append(')');
                process(left, right + 1);
                temp.deleteCharAt(temp.length() - 1);
            }
        }
    }
}

class Question23 {

    public ListNode mergeKLists(ListNode[] lists) {
        return process(lists, 0, lists.length - 1);
    }

    public ListNode process(ListNode[] lists, int left, int right) {// 二分递归
        if (left > right) {
            return null;
        }
        if (left == right) {
            return lists[left];
        }
        if (left + 1 == right) {
            return merge(lists[left], lists[right]);
        }
        int mid = (left + right) / 2;
        return merge(process(lists, left, mid), process(lists, mid + 1, right));
    }

    public ListNode merge(ListNode l1, ListNode l2) {// 合并链表
        ListNode vir = new ListNode(), head = vir, temp = null;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                temp = new ListNode(l1.val);
                head.next = temp;
                head = temp;
                l1 = l1.next;
            } else {
                temp = new ListNode(l2.val);
                head.next = temp;
                head = temp;
                l2 = l2.next;
            }
        }
        while (l1 != null) {
            temp = new ListNode(l1.val);
            head.next = temp;
            head = temp;
            l1 = l1.next;
        }
        while (l2 != null) {
            temp = new ListNode(l2.val);
            head.next = temp;
            head = temp;
            l2 = l2.next;
        }
        return vir.next;
    }

//    public static ListNode mergeKLists(ListNode[] lists) {
//        ListNode virtual=new ListNode();
//        ListNode result=virtual;
//        while (true){
//            ListNode curMin=null;
//            int minIndex=-1;
//            for (int i=0;i< lists.length;i++){
//                if (lists[i]==null) continue;
//                if (curMin==null) {
//                    curMin=lists[i];
//                    minIndex=i;
//                }
//                else if (curMin!=null&&lists[i].val< curMin.val){//寻找到最小的节点，并记录该节点再数组中的位置
//                    curMin=lists[i];
//                    minIndex=i;
//                }
//            }
//            if (minIndex!=-1) lists[minIndex]=lists[minIndex].next;//最小下标的链表向后移动
//            if (curMin==null) break;
//            result.next=curMin;//将最小的节点接入
//            result=result.next;
//        }
//        return virtual.next;
//    }
}

class Question24 {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }
}

class Question25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode vir = new ListNode(0), pre = head, last = vir, nextStart = null;
        List<ListNode> list = new ArrayList<>();
        vir.next = head;
        while (true) {
            int j = 0;
            for (j = 0; j < k && pre != null; j++) {//收集本段节点
                list.add(pre);
                pre = pre.next;
            }
            if (pre == null && j != k) break;//不满足整段，跳出
            else {
                nextStart = list.get(list.size() - 1).next;//下一段开始节点
                while (!list.isEmpty()) {//本段翻转
                    last.next = list.get(list.size() - 1);
                    list.remove(list.size() - 1);
                    last = last.next;
                }
                pre = nextStart;//进入下一段
            }
        }
        last.next = nextStart;
        return vir.next;
    }
}

class Question26 {
    public static int removeDuplicates(int[] nums) {
        int flag = nums[0] - 3;//确定重复元素的替代值
        for (int i = 0; i < nums.length - 1; i++) {//直到判断到倒数第二个
            int temp = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (temp == nums[j]) nums[j] = flag;//出现了重复数字改变数字的值
            }
        }
        for (int i = 1; i < nums.length; i++) {//将所有被标记重复的数字置换到最后
            for (int j = 0; j < nums.length - 1; j++) {
                if (nums[j] == flag) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        int count = 0;
        for (Integer temp : nums) {
            if (temp != flag) count++;
        }
        return count;
    }
}

class Question27 {
    public static int removeElement(int[] nums, int val) {
        for (int i = 0, j = nums.length - 1; i < nums.length && i <= j; i++) {
            if (nums[i] == val && nums[j] != val) {//当头指针为目标值，尾指针不为目标值，交换
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                j--;
            } else if (nums[i] == val && nums[j] == val) {//当头指针为目标值，尾指针也为目标值，尾指针移动
                i--;
                j--;
            }
        }
        int count = 0;
        for (Integer integer : nums) if (integer != val) count++;
        return count;
    }
}

class Question28 {
    public static int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        char[] s = haystack.toCharArray(), p = needle.toCharArray();
        // 枚举原串的「发起点」
        for (int i = 0; i <= n - m; i++) {
            // 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
            int a = i, b = 0;
            while (b < m && s[a] == p[b]) {
                a++;
                b++;
            }
            // 如果能够完全匹配，返回原串的「发起点」下标
            if (b == m) return i;
        }
        return -1;
    }
}

class Question29 {
    public int process(long dividend, int divisor) {
        if (dividend < divisor) return 0;
        long temp = divisor;
        int result = 1;
        while (dividend > (temp + temp)) {
            result = result + result;//翻倍
            temp = temp + temp;
        }
        result += process(dividend - temp, divisor);
        return result;
    }

    public int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        int result = 0, flag = 1;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) flag = -1;
        long tempdividend = Math.abs(dividend);//恒正
        divisor = Math.abs(divisor);
        result = process(tempdividend, divisor);
        return result * flag;
    }
}